/*
题目: 可能的二分法
给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

https://leetcode.cn/problems/possible-bipartition/
 */
public class PossibleBipartition {
    int[] status = null;
    int n ;

    public boolean  (int n, int[][] dislikes) {
        this.n = n;
        // 记录每一个人的分组情况, 0 表示未分组, 1 表示划分为 A 组, -1 表示划分为 B 组
        status = new int[n + 1];

        // 记录每个人不想和 谁 分组
        // 数组 + 线性表
        List<Integer>[] group = new List[n + 1];
        for (int i = 1; i <= n; i ++)  group[i] = new ArrayList<> ();

        for (int cur[] : dislikes) {
            group[cur[0]].add(cur[1]);
            group[cur[1]].add(cur[0]);
        }

        for (int i = 1; i <= n; i ++) {
            // 如果没有分组, 还冲突了, 就返回 false, 默认划分为 A 组
            if (status[i] == 0 && !dfs(i, group, 1)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int pos, List<Integer>[] group, int color) {
        status[pos] = color;
        // 对这个同学讨厌的人划分为另一个组
        for (int p : group[pos]) {
            // 讨厌的同学被划分为一个组
            if (status[p] == color) {
                return false;
            }
            // 如果还没分组, 就进行划分为另一个组
            if (status[p] == 0 && !dfs(p, group, -color)) {
                return false;
            }
        }
        return true;
    }
}
